|
1.
基于Ncut准则的图分割的新算法
周德新 王兴旺 刘涛
计算机应用
2010, 30 (12):
3262-3264.
针对有权图分割时不能很好解决子图内部耦合度不高的问题,使用可以同时优化子图内部顶点耦合度和子图之间顶点耦合度的Ncut准则,提出了一种新的基于迭代改善策略的RNK分割算法。算法通过不断交换可以改善Ncut值的顶点对优化现有分割。与传统分割算法相比,可以同时保证子图内最大耦合度和子图间最小的耦合度。并提出一种散列技术,提高查找最优交换顶点对的效率。当图为稠密矩阵时,改善效果尤为明显。通过对随机图分割的实验结果表明,该算法较传统的KL算法可以得到更理想的分割结果。
相关文章 |
多维度评价
|
|